Computer implemented multipliers are crucial in modern computer systems. Many different applications, including, but not limited to, linear programming, digit multiplication, vector graphics and others, use computer implemented multipliers.
One conventional way of doing multiplication in computers has been based on the conventional, paper-and-pencil technique known as repeated addition. Consider the example of (27)10*(27)10=(729)10.
FIG. 1 illustrates how this may be done by a computer. First the computer takes the binary version of 27=110112. Then, the second 110112 is added to the first version. For the each of the five digits of the second 110112, a row is formed; row 100 is for the lowest significance digit, and row 102 is for the next highest significance digit. The third highest significance digit, for row 104, is a 0, thereby forming a row of zeros. Similarly, rows 106 and 108 are formed.
All of the rows are added together to form the final value 10110110012=72910.
Note that when digits are multiplied in this way, 2n2 units of memory storage are required. In addition, there are nine columns to be added, and hence the total addition may include as many as eight carry bits.
The above describes one technique of multiplication on a computer, and it should be understood that there are other such techniques. While the above describes that the amount of storage that is needed grows quadratically with the number of bits, other techniques may scale more or less than this.
In addition, various ways have been used to improve the speed of operation of such a system, and also to minimize the amount of memory storage needed to multiply in this way. Computer hardware and software may operate using bit-shift, look ahead, parallel read, pipeline, table lookup, and other techniques. Booth encoding, 2's compliment representation of signed binary numbers, the composition or partitioning of the number into parts, binary trees, and other similar techniques to improve and increase the speed of this multiplication and to reduce the complexity of the multiplication process.